Searchable encryption is a technique that allows searching while search target data and search content remain encrypted.
In recent years, with the spread of cloud services and the like, data management on the Internet has become possible. However, for the data management on the Internet, there are risks such that a server such as a cloud which is an outsourcing contractor of the data management may be infected with malware such as a computer virus, and that an administrator of the server may commit fraud, thereby leaking outsourced data to the outside. If the data outsourced to the server is personal information or confidential corporate data, this leakage is a serious problem.
There is an encryption technique as a method to avoid such a security threat. However, if data is simply encrypted and stored in the server, there arises a problem that searching of the data cannot be performed. In order to avoid this problem, there has been devised a method in which when a search is performed, encrypted data stored on the server is once decrypted to then perform the search. However, the data returns to plaintext for a certain period of time in the server, so that this method cannot be regarded as adequate as a countermeasure.
Therefore, a “searchable encryption technique” which is a cryptographic technique that allows searching while data remains encrypted has been devised. Many specific methods of the searchable encryption technique have been disclosed in recent years.
In the searchable encryption technique, schemes that allow “exact match searching” which is simple searching (see Non-Patent Literature 1, for example) have been mainly considered. In recent years, schemes that allow more flexible searching, for example, “partial match searching” (see Patent Literature 1 and Non-Patent Literature 2, for example), schemes that allow “similarity searching” (see Non-Patent Literature 3 and Non-Patent Literature 4, for example), and the like have also been considered. Hereinafter, a scheme that allows partial match searching will be referred to as a “searchable encryption technique with partial matching”, and a searchable encryption technique that allows similarity searching will be referred to as a “similarity searchable encryption technique”.
The searchable encryption technique is broadly divided into two types, schemes based on public-key cryptography and schemes based on common-key cryptography.